/* http://en.wikipedia.org/wiki/Longest_common_subsequence_problem */
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

/*
 * dynamic programming
 * optimizations:
 * a) if several first/last chars are equals, they can be eliminated.
 * b) if only the length is required, matrix is not necessary, only one row will do the job.
 */
string longest_common_subsequence(const string &a, const string &b) {
    int i, j, **matrix;
    string res;
    matrix = new int*[a.length()+1];
    for (i = 0; i <= a.length(); i++) {
        matrix[i] = new int[b.length()+1]();
    }
    /* fill in matrix */
    for (i = 1; i <= a.length(); i++) {
        for (j = 1; j <= b.length(); j++) {
            if (a[i-1] == b[j-1]) {
                matrix[i][j] = matrix[i-1][j-1] + 1;
            } else {
                if (matrix[i][j-1] < matrix[i-1][j]) {
                    matrix[i][j] = matrix[i-1][j];
                } else {
                    matrix[i][j] = matrix[i][j-1];
                }
            }
        }
    }
#if 0 /* output */
    for (i = 1; i <= a.length(); i++) {
        for (j = 1; j <= b.length(); j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
#endif
    /* search in reverse order, return only one result. */
    i = a.length(), j = b.length();
    while (i >= 1 && j >= 1) {
        if (a[i-1] == b[j-1]) {
            res.push_back(a[i-1]);
            i--;
            j--;
        } else {
            if (matrix[i][j-1] < matrix[i-1][j]) {
                i--;
            } else {
                j--;
            }
        }
    }
    /* free */
    for (i = 0; i <= a.length(); i++) {
        delete[] matrix[i];
    }
    delete[] matrix;
    std::reverse(res.begin(), res.end());
    return res;
}

/* LIS can be implemented via LCS */
string longest_increasing_subsequence(const string &s) {
    string s2 = s;
    std::stable_sort(s2.begin(), s2.end());
    return longest_common_subsequence(s2, s);
}

int main() {
    string a = "ABCBDAB";
    string b = "BDCABA";
    string r = longest_common_subsequence(a, b);
    cout << r << endl;
    string s = "ADEACDFGIKJPQSTUZX";
    r = longest_increasing_subsequence(s);
    cout << r << endl;
    return 0;
}

